Routing System

The goal is to convert a curve network into a set of closed cycles (i.e. sequences of curves) that form mesh patches. The core algorithm is based on prior works in cycle search algorithms on curve networks (Liu and Lee 2001; Varley and Company 2010; Zhuang et al 2013). This class of algorithms convert the curve newtork into a cycle graph, and perform search over the cycles to find the optimal cycle set guided by some geometric or topological costs. Following the same technique, we define the following objects, together known as a routing system, over which we search for the opitmial subset:

• Dart: A point at an end of a curve. For a curve with degree $k$, each end point has $k$ darts. Darts are used to connect to other darts on other curves across a vertex.
• Corner: A pair of curves that are connected at a vertex in a cycle.
• Corner mapping: A mapping from a dart at a vertex to a different dart at the same vertex.
• Bridge: A sequence of three curves that are connected in a cycle.
• Bridge mapping: A mapping from a dart at one end of a curve to a dart at another end of the same curve.

A routing system can describe any set of cycles on a curve network by decomposing a curve into bridge mappings and vertices into corner mappings. Therefore, the sketch-to-mesh algorithm aims to find a routing system of the curve network, from which we can recover the cycles. In particular, we iteratively search the space of routing systems to minimize a cost function that determines how "nice" the cycles are. More formally, we define two types of cost functions, intra-bridge cost and inter-bridge cost.

Intra-bridge Cost

The intra-bridge cost is a cost function that favors smooth normal transition at a (nontrivial) vertex. More formally, given a pair of curves $c_1$ and $c_2$ meeting at a vertex $v$, and a normal $n_1$ on $c_1$ at $v$, we parallel transport $n_1$ to curve $c_2$ to get $n_2$. Then we measure the following two angles:

• Bending angle: The angle $\theta_0$ formed by $n_1$ and $n_2$. The bending angle measures the smoothness of the underlying patch at the corner.
• Interior angle: Let $t_1$ be the tangent of $c_1$ at $v$, let $t_2$ be the tangent of $c_2$ at $v$, and let $l = n_1 \times (t_1 + t_2)$. Intuitively, $l$ is the bisecting vector of the corner on the underlying patch. The interior angle is defined as the sum of angle $\theta_1$ between $t_1$ and $l$ and the angle $\theta_2$ between $t_2$ and $l$. This angle measures the convexity of the underlying

The intra-bridge cost is defined as the sum of the bending angle and the interior angle, namely $\theta_0 + \theta_1 + \theta_2$.

Inter-bridge Cost

The inter-bridge cost is a cost function that favors the set of bridges (i.e. triplets of curves) that meet at the middle curve with small normal discontinuity. More formally, given a routing system, find the set of all bridges centered at curve $b$, i.e. $\{a_i, b, c_i\}$ for $i \in [1, k]$ where $k$ is the capacity of the curve. Let $\alpha_i$ be the angle formed by normals $n_i$ and $n_{i+1}$. The inter-bridge cost is defined as $k\sqrt{\frac{\sum_{i=1}^k(\pi - \alpha_i)^2}{k}} - (k-2) \pi$